//输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
//
// 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
//
//
//
// 示例 1：
//
//
//输入：n = 12
//输出：5
//
//
// 示例 2：
//
//
//输入：n = 13
//输出：6
//
//
//
// 限制：
//
//
// 1 <= n < 2^31
//
//
// 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/
//
// Related Topics 递归 数学 动态规划 👍 433 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 超时写法
function countDigitOneOverTime(n: number): number {
    let count = 0
    for (let i = 1; i <= n; i ++) {
        count += countOne(i)
    }
    return count
};
function countOne(num) {
    let count = 0
    //? 1234151
    while (num !== 0) {
        if (num % 10 === 1) count += 1
        num = Math.floor(num / 10)
    }
    return count
}
//leetcode submit region end(Prohibit modification and deletion)
//? 思路应该是统计每个位数上有多少个1而不是每个都计算
function countDigitOne(n: number): number {
    //? 1283782
    //? 1232131
    //? 12312900
    let high = Math.floor(n / 10), cur = n % 10, low = 0, digit = 1
    let res = 0
    while(high != 0 || cur != 0) {
        /* *
          * 由于是计算每个位数的1的数量 以23x4中的十位出现1的情况 分为三种情况
          * 1.十位为0：
          * 即2304 我们先锁住十位，强行让十位变成1，剩下三位可以随意滚动：XX1X。那么求十位出现一的个数也就是，我可以滚出多少种密码组合，使得该密码小于等于n（注意十位被锁定成了1，转不动）。
          * 不难发现，我们能滚出的最大数是：2219,我们能滚出的最小数是：0010。
          * 那么0010到2219之间有多少种十位为1的密码呢？我们去掉十位，得到000和229。一共就是229-000+1 = 230种。即对于十位为0的情况来说，就是千位和百位构成的数*10。
          * 2.十位为1：
          * 即2314 我们先锁住十位，强行让十位变成1，剩下三位可以随意滚动：XX1X。那么求十位出现一的个数也就是，我可以滚出多少种密码组合，使得该密码小于等于n（注意十位被锁定成了1，转不动）。
          * 不难发现，我们能滚出的最大数是：2314,我们能滚出的最小数是：0010。
          * 那么0010到2314之间有多少种十位为1的密码呢？我们去掉十位，得到000和234，一共就是23*10+4+1 = 235种。即千位和百位构成的数*10 + n个位的数字+1.
          * 3.十位为2-9：
          * 即2324(例) 我们先锁住十位，强行让十位变成1，剩下三位可以随意滚动：XX1X。那么求十位出现一的个数也就是，我可以滚出多少种密码组合，使得该密码小于等于n（注意十位被锁定成了1，转不动）。
          * 不难发现，我们能滚出的最大数是：2319,我们能滚出的最小数是：0010。
          * 那么0010到2319之间有多少种十位为1的密码呢？我们去掉十位，得到000和239，一共就是239-000+1 = 240种。也是（23+1）*10 = 240种。即(n万位和千位构成的数+1)*10.
          * 如果我们定义十位左边的数为高位，例如2304的高位为23，十位右边的数为低位，例如2304的低位为4，那么以上规律就可以写成高位和低位的规律。我们分别对2304的每一位做一次分析，并将四部分结果相加就得到了答案。
        * */
        //? 此位数上数字为0
        if (cur == 0) {
            //? (high)构成的数*10
            res += high * digit
        }
        //? 此位数上数字为1
        else if (cur == 1) {
            //? (high)构成的数*10 + n个位的数字(low) + 1
            res += high * digit + low + 1
        }
        //? 此位数上数字为非0,1
        else {
            //? ((high)构成的数+1)*10
            res += (high + 1) * digit
        }
        //? 统计每个位数上的数是多少
        low += cur * digit
        //? cur取下一个位数上的数
        cur = high % 10
        //? high接着减小 变更高位
        high = Math.floor(high / 10)
        //? 位数增加
        digit *= 10
    }
    return res
};
